import java.awt.Point;
import java.awt.Shape;
import java.awt.geom.Point2D;
import java.awt.geom.Point2D.Double;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;


public class SRTAlgorithm implements GlobalSettings{

	double aggregatex[]=new double[trees.size()];
	double aggregatey[]=new double[trees.size()]; 
	
	int indexMatrix[][]=new int[trees.size()][trees.size()];//To check duplication of tree
		
	SRTAlgorithm(){
		for(int i=0;i<trees.size();i++)
		{
			Nt.add(new ArrayList<ArrayList<Point>>());
			indexMatrix[i][i]=1;
			for(int j=0;j<trees.size();j++)
				connectedMatrix[i][j]=-1;
		}
	}
	
	void generateRoadMap()
	{
		
		System.out.println("Generating Roadmap");
		int i=0;
		double d;
		
		//System.out.println("No. of trees="+trees.size());
		for(ArrayList<Point> tree:trees)//Calculate aggregate configuration for each tree
		{
			aggregatex[i]=0;
			aggregatey[i]=0;
			for(Point p:tree)
			{
				aggregatex[i]+=p.x;
				aggregatey[i]+=p.y;
			}
			aggregatex[i]=aggregatex[i]/tree.size();
			aggregatey[i]=aggregatey[i]/tree.size();
			i++;
		}
		/*System.out.println("trees are");
		for(int j=0;j<trees.size();j++)//ArrayList<Point> tree:trees)
		{
			System.out.println(trees.get(j));
		}*/
		//int j=0;
		for(int j=0;j<trees.size();j++)//ArrayList<Point> tree:trees)
		{
			ArrayList<Point> tree=trees.get(j);
			ArrayList<TreeDistance> distances=new ArrayList<TreeDistance>();//To sort distances of k-nearest trees
			Random r=new Random();
			//ArrayList<Integer> indexList=new ArrayList<Integer>();//To check duplication of trees in Nt(j)
			for(i=0;i<trees.size();i++)
			{
				if(i!=j){
					d=getDistance(aggregatex[j],aggregatey[j],aggregatex[i],aggregatey[i]);
					distances.add(new TreeDistance(i,d));
				}	
				else
					distances.add(new TreeDistance(i,1000));
			}
			Collections.sort(distances,new TreeDistance());
			i=0;//index in sorted list of distances
			while(Nt.get(j).size()<kNeartrees && i<distances.size())//get k nearest neigbours
			{
				if(indexMatrix[distances.get(i).treeIndex][j]==0)
				{
					//System.out.println(distances.get(i).treeIndex+" added");	//Add bi-directional edges			
					Nt.get(j).add(trees.get(distances.get(i).treeIndex));		
					Nt.get(distances.get(i).treeIndex).add(trees.get(j));
					indexMatrix[distances.get(i).treeIndex][j]=1;
					indexMatrix[j][distances.get(i).treeIndex]=1;
				}
				i++;
			}
			//System.out.println("After knn="+Nt.get(j).size());
			Integer s;
			int k=0;
			while(k<randomTrees)
			{
				s=r.nextInt(trees.size());
				if(indexMatrix[s][j]==0)
				{
					Nt.get(j).add(trees.get(s));
					Nt.get(s).add(trees.get(j));
					indexMatrix[s][j]=1;
					indexMatrix[j][s]=1;
					k++;
				}						
			}
			//Done with finding neighbours
			//Do following for each neighbours
			boolean merged;
			for(int q=0;q<trees.size();q++)
			{
					if(j!=q && indexMatrix[j][q]==1 && connectedMatrix[j][q]==-1)
					{
						ArrayList<Point> tj=trees.get(q);
						merged=false;
						ArrayList<Point> si=new ArrayList<Point>();
						for(int z=0;z<randomConfig;z++)
						{
							int randomPoint=r.nextInt(tree.size());
							if(!si.contains(tree.get(randomPoint)))
								si.add(tree.get(randomPoint));
						}
						for(Point qi:si)
						{
							//System.out.println("1st loop");
							if(merged==false)
							{
								Point qj=getClosestConfig(tj,qi);
								//System.out.println("Checking freepath("+qi+","+qj+")");
								if(isFreePath(qi,qj))
								{
									startConnectTreePoints.add(qi);
									endConnectTreePoints.add(qj);
									merged=true;
									connectedMatrix[j][q]=startConnectTreePoints.size()-1;
									connectedMatrix[q][j]=endConnectTreePoints.size()-1;									
								}
							}
							
						}
						if(merged==false)
						{
							for(Point qi:tree)
							{
							//	System.out.println("2nd loop");
								for(Point qj:tj){
								//	System.out.println("Checking freepath("+qi+","+qj+")");
									if(isFreePath(qi,qj))
									{
										startConnectTreePoints.add(qi);
										endConnectTreePoints.add(qj);
										merged=true;
										connectedMatrix[j][q]=startConnectTreePoints.size()-1;
										connectedMatrix[q][j]=endConnectTreePoints.size()-1;
										break;
									}
								}
								if(merged==true)
									break;
							}
						}
					}
			}
			//System.out.println("After random="+Nt.get(j).size());
	    }
		/*for(int j=0;j<trees.size();j++)
		{
			System.out.println("Neighbour of"+ trees.get(j));
			for(ArrayList<Point> l:Nt.get(j))
				System.out.println(l);
			System.out.println("Next");
		}*/
}
	private Point getClosestConfig(ArrayList<Point> tj, Point qi) {
		// TODO Auto-generated method stub
		double d=dmin,dist;
		Point minPoint=null;
		for(Point pt:tj)
		{
			if(d>(dist=getDistance(pt.x,qi.x,pt.y,qi.y)))
			{
				d=dist;
				minPoint=pt;
			}
				
		}
		return minPoint;
	}

	private double getDistance(double d, double e, double f, double g) {
		// TODO Auto-generated method stub
		
		return Math.sqrt((d-f)*(d-f)+(e-g)*(e-g));
	}
	
	public boolean isFreePath(Point p1, Point p2) {
		// TODO Auto-generated method stub
			Point2D.Double qnear=new Point2D.Double();
			Point2D.Double qnew=new Point2D.Double();
		    qnear.x=p1.x*(windowSizeY/gridCount)+5;
		    qnear.y=p1.y*(windowSizeX/gridCount)+5;
		    qnew.x=p2.x*(windowSizeY/gridCount)+5;
		    qnew.y=p2.y*(windowSizeX/gridCount)+5;
		   // System.out.println("checking "+qnear+"to"+qnew);
			if(qnear.x==qnew.x)
			{
				if(qnear.y<qnew.y)
				{
					for(double i=qnear.y+1;i<=qnew.y;i++)
						if(!isFree(new Point2D.Double(qnear.x,i)))
							return false;
				}
				if(qnear.y>qnew.y)
				{
					for(double i=qnew.y+1;i<=qnear.y;i++)
						if(!isFree(new Point2D.Double(qnear.x,i)))
							return false;
				}
			}
			if(qnear.y==qnew.y)
			{
				if(qnear.x<qnew.x)
				{
					for(double i=qnear.x+1;i<=qnew.x;i++)
						if(!isFree(new Point2D.Double(i,qnear.y)))
							return false;
				}
				if(qnear.x>qnew.x)
				{
					for(double i=qnew.x+1;i<=qnear.x;i++)
						if(!isFree(new Point2D.Double(i,qnear.y)))
							return false;
				}
			}
			double y;
			if(qnear.x<qnew.x)
				for(double i=qnear.x+1;i<=qnew.x;i++)
				{
					y=((qnew.y-qnear.y)/(qnew.x-qnear.x))*(i-qnear.x)+qnear.y;
						if(!isFree(new Point2D.Double(i,y)))
							return false;
				}
			else
				for(double i=qnew.x+1;i<=qnear.x;i++)
				{
					y=((qnew.y-qnear.y)/(qnew.x-qnear.x))*(i-qnear.x)+qnear.y;
						if(!isFree(new Point2D.Double(i,y)))
							return false;
				}
		return true;
	}

		private boolean isFree(Double double1) {
			// TODO Auto-generated method stub
			//if(fillMatrix[(int)Math.floor(point.x/gridCount)][(int)Math.floor(point.y/gridCount)])
			for (Shape shape : fill) {
                if (shape.contains(double1)) {
                	return false;
                }
    		}	
			return true;
		}
	/*public boolean isFreePath(Point qnear, Point qnew) {
		// TODO Auto-generated method stub
			int dx=Math.abs(qnear.x-qnew.x),sx= qnear.x<qnew.x? 1:-1;
			int dy=Math.abs(qnear.y-qnew.y),sy= qnear.y<qnew.y? 1:-1;
			int err=(dx>dy ? dx: -dy)/2,e2;
			int x0=qnear.x,y0=qnear.y;
			int x1=qnew.x,y1=qnew.y;
			
			for(;;){
				if(!isFree(new Point(x0,y0)))
						return false;
				if(x0==x1 && y0==y1) break;
				e2=err;
				if(e2>-dx){ err-=dy; x0+=sx;}
				if(e2<dy) { err+=dx;y0+=sy;}
			}
			return true;
	}

		private boolean isFree(Point point) {
			// TODO Auto-generated method stub
			if(point.x>=gridCount || point.x<0 || point.y>=gridCount || point.y<0)
				return false;
			if(fillMatrix[point.x][point.y])
				return false;
			return true;
		}*/
}